#ifndef ALGORITHM_TABU__
#define ALGORITHM_TABU__

#include <cmath>

#include "algorithm.h"
#include "area.h"
#include "options_tabu.h"
#include "test_manager.h"

/** Historie tabu pohybu. Rozhoduje, zda je zvoleny pohyb tabu, nebo ne.
 */
class TabuHistory {
public:
	typedef std::list<std::pair<int, int> > HistoryField;
	typedef HistoryField::iterator HistoryIterator;
	/** Defaultni konstruktor inicializujici historii.
	 * \param size pocet vysilacu na mape
	 * \param length delka kratkodobe historie
	 * \param rate povoleny pomer zmen vysilace v dlouhodobe historii
	 */
	TabuHistory(int size, int length, double rate): size(size), length(length), rate(rate), round(1) {
		history = new HistoryField[size];
		energy = MAXINT;
	}
	bool IsTabu(int antena, int frequency);
	/** Informuje historii o prechodu do stavu s novou energii.
	 * \param energy nova energie
	 */
	void RoundEnergy(int energy) {
		if (energy < this->energy) {
			this->energy = energy;
		}
	}
	/** Vraci doposud nejmensi dosazenou energii reseni.
	 * \return nejmensi energie reseni v historii 
	 */
	int MinEnergy() {
		return energy;
	}
	void Add(int antena, int frequency);
	void Clear();
	/** Vraci cislo aktualniho kroku.
	 * \return cislo aktualniho kroku
	 */
	int Round() {
		return round;
	}
private:
	int size, ///< pocet vysilacu na mape
		length, ///< delka kratkodobe historie
		round; ///< cislo aktualniho kola
	int energy; ///< nejmensi dosazena energie
	double rate; ///< maximalni povoleny pomer poctu zmen jednoho vysilace ku poctu vsem zmen
	HistoryField * history; ///< historie frekvenci prirazena jednotlivym vysilacum
};

/** Informace o tabu pohybu.
 */
class TabuChange {
public:
	/** Defaultni konstruktor.
	 * \param antena meneny vysilac
	 * \param frequency nova frekvence
	 */
	TabuChange(int antena, int frequency): antena(antena), frequency(frequency), energy(MAXINT) {}
	/** Prazdny konstruktor. */
	TabuChange(): antena(0), frequency(0), energy(MAXINT) {}
	int antena, ///< cislo meneneho vysilace
		frequency; ///< nova frekvence meneneho vysilace
	int energy; ///< energie reseni dosazeneho touto zmenou
};

/** Abstraktni trida reprezentujici reseni tabu search algoritmu. Umoznuje vygenerovat vsechny sousedy
 * aktualniho reseni, vybrat z nich nejlepsiho a prejit do nej. Pamatuje si vysilace, ktere porusuji
 * nejake podminky.
 */
class TabuSolution {
public:
	/** Defaultni konstruktor. Alokuje pamet pro pamatovani vysilacu rusicich podminky.
	 * \param area mapa problemui
	 * \param options nastaveni tabu search algoritmu
	 */
	TabuSolution(Area * area, TabuOptions * options): area(area), options(options), energy(0), count(0), history(area->size, options->history, options->alpha)  {
		violating = new int[area->size];
	}
	/** Destruktor, vraci pouzitou pamet.
	 */
	~TabuSolution() {
		delete[] violating;
	}
	/** Vraci energii reseni.
	 * \return energie reseni
	 */
	int Energy() {
		return energy;
	}
	/** Vycisti historii vsech pohybu.
	 */
	void ClearHistory() {
		history.Clear();
	}
	/** Vraci pocet vysilacu porusujici podminky.
	 * \return pocet porusujicich vysilacu
	 */
	int ViolatingCount() {
		return count;
	}
	/** Vraci cislo aktualniho kroku algoritmu.
	 * \return cislo aktualniho kroku
	 */
	int LoopNumber() {
		return history.Round();
	}
	/** Virtualni metoda urcena k nacteni celeho sousedstvi.
	 * \param frequencies pocet frekvenci, ktere je mozne pouzit pro tvorbu sousedstvi (maximalni povolena frekvence)
	 */
	virtual void GetNeighbours(int frequencies) = 0; // find out the neighborhood
	/** Virtualni metoda urcena k rozpoznani nejlepsiho prvku v sousedstvi a prechodu do nej.
	 */
	virtual void MoveToBest() = 0; // select the best solution from the generated neighborhood
	void LowerFrequencies(int & frequencies);
protected:
	void CountEnergy(TabuChange & change);
	void MoveTo(TabuChange & change); // change the solution according to the specified change
	void UpdateViolations();
	int energy; ///< energie aktualniho reseni
	int count, ///< pocet vysilacu porusujicich podminky
		* violating; ///< seznam vysilacu porusujicich podminky
	TabuHistory history; ///< historie vsech pohybu k urcovani, zda je pohyb tabu
	Area * area; ///< mapa problemu
	TabuOptions * options; ///< nastaveni tabu search algoritmu
};

/** Reseni tabu search algoritmu pouzivajici jako sousedstvi omezene nahodne sousedstvi.
 * V sousedstvi je predem dany pocet reseni, kazde vznikne zmenou frekvence nahodneho porusujiciho
 * vysilace na nahodnou jinou frekvenci.
 */
class TabuRandomSolution: public TabuSolution {
public:
	/** Inicializace reseni, alokace potrebnych datovych struktur pro zapamatovani celeho sousedstvi.
	 * \param area mapa problemu
	 * \param options nastaveni tabu search algoritmu
	 */
	TabuRandomSolution(Area * area, TabuOptions * options): TabuSolution(area, options) {
		neighbours = new TabuChange[area->size];
	}
	/** Odalokovani pouzitych struktur.
	 */
	~TabuRandomSolution() {
		delete neighbours;
	}
	void GetNeighbours(int frequencies); // find out the neighborhood
	void MoveToBest(); // select the best solution from the generated neighborhood
private:
	TabuChange * neighbours; ///< pole vsech sousednich reseni
};

/** Tabu search algoritmus. Optimalizacni algoritmus zalozeny na vylepsovani aktualniho reseni.
 * V kazdem kroku je vygenerovano sousedstvi, aktualni reseni je pak nahrazeno nejlepsim resenim v sousedstvi.
 * Zacykleni je braneno historii tabu pohybu, ktera znemoznuje prilisny navrat pohybu.
 */
class TabuAlgorithm: public Algorithm {
public:
	/** Defaultni konstruktor tabu search algoritmu.
	 * \param o nastaveni tabu search
	 */
	TabuAlgorithm(Options * o): Algorithm(o), options((TabuOptions *)o) {}
	/** Konstruktor rovnou prirazujici i mapu se zadanim.
	 * \param a mapa zadani
	 * \param o nastaveni tabu search algoritmu
	 */
	TabuAlgorithm(Area * a, Options * o): Algorithm(o), options((TabuOptions *)o) {
		area = a;
	}
	/** Dalsi reseni neni mozne nacist.
	 * \return vzdy false
	 */
	bool Next() {
		return false;
	}
	bool Solve();
	/** Do logu vypise informace o nastaveni tabu search algoritmu.
	 */
	void PrintInfo() {
		options->Log() << "Tabu Search (hledani tabu) - sestava z vygenerovani "
			<< "pocatecniho reseni pomoci sekvenciho algoritmu. Pote se pokousi vzdy odstranit nejvetsi "
			<< "frekvenci (vsechny anteny, ktere ji pouzivaly, jsou prenastaveny na nizsi frekvence)." << std::endl;
		options->Print();
	}
	/** Vraci popis nastaveni algoritmu.
	 * \return popis nastaveni algoritmu
	 */
	std::string GetDetail() {
		return "tabu: " + options->GetTitle();
	}
private:
	void CountEnergy(TabuSolution & solution);
	void GetNeighbour(TabuSolution & base, TabuSolution & neighbour);
	void LowerFrequencies(TabuSolution & solution);
	TabuOptions * options; ///< nastaveni tabu search algoritmu
};

#endif
